/**
 * 希尔排序
 *      算法思想：在直接排序的基础上，进行优化
 *      缩小增量
 * @param {*} list 
 */
function shellSort (list) {
    const d = cut(list) // 增量序列
    let k = 0,x,i,j
    while (k < d.length) {
        for (i = d[k]; i < list.length; i++) {
            x = list[i]
            j = i - d[k]
            while (j >= 0 && list[j] > x) {
                list[j + d[k]] = list[j]
                j = j - d[k]
            }
            list[j + d[k]] = x
        }
        k++
    }
    return list
}

function cut (list) {
    let res = [], d = Math.floor(list.length/2)
    for (let i = 0; d >= 1; i++) {
        res[i] = d
        d = Math.floor(d/2)
    }
    return res
}

console.log(shellSort([1,2,45,8,1,78,100,456,12,0]))